﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using Flight_Reservation.DataLayer;


namespace Flight_Reservation.Algorith_Rasmus
{
    public class Dijkstras
    {
        private DBRoute dbr;
        private List<Route> routes;//List of all routes in the database

        public Dijkstras()
        {
            dbr = new DBRoute();
            routes = AllRoutes();
        }

        private List<Route> AllRoutes()//Gets all Routes from the database using DBRoute
        {
            return dbr.GetAllRoutes2();
        }

        private List<Route> GetAdjecencies(Airport airport)//Returns all routes going out from a given airport
        {
            List<Route> adjacentRoutes = new List<Route>();
            foreach(Route route in routes.Where(r => r.StartAirport.AirportCode == airport.AirportCode))
            {
                adjacentRoutes.Add(route);
            }
            return adjacentRoutes;
        }

        public List<SolutionPath> FindViablePaths(Airport destination, int maxLayovers)//Returns a list of the shortest path from an airport to all other airports within the maxLayovers limit
        {
            List<SolutionPath> viableRoutes = new List<SolutionPath>();//The list we return
            viableRoutes.Add(new SolutionPath(destination));//Add a dummy solutionpath to have a staring point
            for (int i = 0; i < viableRoutes.Count; i++)//Running through the viable routes found including the ones we find during the loop
            {
                foreach (Route route in GetAdjecencies(viableRoutes[i].Destination()))
                {

                    if (!viableRoutes.Any(s => s.Destination().AirportCode == route.EndAirport.AirportCode) && viableRoutes[i].GetRoutes().Count < maxLayovers + 2)
                    {//If we havent found a path to the the end of a route before and if its within the maxLayovers limit
                        SolutionPath solutionPath = new SolutionPath();
                        foreach (Route r in viableRoutes[i].GetRoutes())
                        {
                            solutionPath.AddRoute(r);//Adding every route from te current viableRoutes object
                        }
                        solutionPath.AddRoute(route);//Adding the current adjecent route
                        viableRoutes.Add(solutionPath);
                    }
                }
            }
            return viableRoutes;
        }

        public List<Route> FindCheapestPath2(Airport start, Airport end, int maxLayovers)
        {
            List<SolutionPath> cheapestPaths = new List<SolutionPath>();//List of the cheapest paths to the airports found
            List<SolutionPath> viablePaths = FindViablePaths(end, maxLayovers);//List of solutionpaths from the destination to every airport within the maxLayovers limit.
            cheapestPaths.Add(new SolutionPath(start));//Adds a starting point for the algorithm
            List<string> allreadyFound = new List<string>();//List of codes for the airports the algoritm have allready found the cheapest path to
            allreadyFound.Add(start.AirportCode);//Adds the starting point as an airport we have allready found the cheapest path to

            if(!viablePaths.Any(s => s.Destination().AirportCode == start.AirportCode))
            {//If the starting point and destination are too far appart compared to the desired maximum amount of layovers there is no point starting the Dijkstras algoritm
                Console.WriteLine("No such route exist");
                return new List<Route>();
            }

            bool timeToStop = false;
            while(!allreadyFound.Contains(end.AirportCode) && !timeToStop)
            {
                List<SolutionPath> possibleSolutions = new List<SolutionPath>();//A list of the possible solutionpaths found in the current run of the algoritm that are to be compared on price before the cheapest is added to the cheapestPaths list
                SolutionPath selectedSolution = new SolutionPath();//This is the object we store the cheapest found solutionpath in before adding it to the cheapestPaths list
                foreach(SolutionPath cheapestPath in cheapestPaths)
                {
                    List<Route> adjecencies = GetAdjecencies(cheapestPath.Destination());//List of routes going from the current cheapestPath in the foreach loop.

                    foreach(Route adjRoute in adjecencies)
                    {
                        if (viablePaths.Any(s => s.Destination().AirportCode == adjRoute.EndAirport.AirportCode) && //If there is a viable path from the current adjRoute's end airport to the destination
                           viablePaths.Single(s => s.Destination().AirportCode == adjRoute.EndAirport.AirportCode).GetRoutes().Count() + cheapestPath.GetRoutes().Count() < maxLayovers + 3//If the total amount of layovers from the current cheapestPath and the rest of the way does not exceed maxLayovers. +3 because of two dummy routes and the destination is no layover
                           && !allreadyFound.Contains(adjRoute.EndAirport.AirportCode))//If we havent allraedy found the cheapest path to the destination of the current adjRoute
                        {
                            SolutionPath possibleSolution = new SolutionPath();
                            foreach(Route route in cheapestPath.GetRoutes())
                            {
                                possibleSolution.AddRoute(route);//We add every route from the current cheapestPath object
                            }
                            possibleSolution.AddRoute(adjRoute);//We add the current adjecent route for a new possible solution
                            possibleSolutions.Add(possibleSolution);
                        }
                    }
                }
                foreach(SolutionPath possibleSolution in possibleSolutions)//We find the cheapest of our possible solutions before adding it to the cheapestPaths list and marking it as found
                {
                    if(possibleSolution.TotalPrice < selectedSolution.TotalPrice || selectedSolution.TotalPrice == 0)
                    {
                        selectedSolution = possibleSolution;
                    }
                }
                cheapestPaths.Add(selectedSolution);
                allreadyFound.Add(selectedSolution.Destination().AirportCode);
                if(selectedSolution.Destination() == null)//If we didn't find any possible solutions selectedSolution will be an empty object and if thats the case its time to stop the algoritm
                {
                    timeToStop = true;
                }
            }
            cheapestPaths.Last().GetRoutes().RemoveAt(0);//We remove the dummy solution path we added as a starting point for the algorithm so we only return the routes we need
            return cheapestPaths.Last().GetRoutes();
        }

        public List<Route> FindCheapestPath(Airport start, Airport end, int maxLayovers)//Returns the cheapest path from the start airport to the end airport with a maximum amount of layovers
        {
            Console.WriteLine("Running cheapest path algorithm");
            List<SolutionPath> solutionPaths = new List<SolutionPath>();//List of the cheapest path's found to every airport
            solutionPaths.Add(new SolutionPath(start));//Adding the start airport to the solutionPaths list

            List<string> nonViableRoutes = new List<string>();//Paths we can't take because it will make us exceed our maxLayovers. This isn't always true and it will make us block ourselves out from a solution in some specifik cases.
            
            List<string> foundPathsTo = new List<string>();//List of codes from the airports we have allready found the cheapest paths to
            foundPathsTo.Add(start.AirportCode);

            int index = 0;
            while(!foundPathsTo.Contains(end.AirportCode) && index < 100)//The algorithm runs until either the cheapest path to the destination is found or until it has looped some amount of time.
            {//Index < 100 is pretty poor coding but we have had a hard time finding something to prevent an eternal loop
                List<SolutionPath> possibleSolutions = new List<SolutionPath>();//List of possible paths to take extending every known solution. PossiblePaths might be a better name
                SolutionPath solutionPath = new SolutionPath();
                foreach(SolutionPath sPath in solutionPaths)//Finds all the current possible solutions originating from solutionPaths, not ending in a place allready found
                {
                    List<Route> adjecencies = GetAdjecencies(sPath.Destination());
                    foreach (Route adjRoute in adjecencies)
                    {
                        if (!foundPathsTo.Contains(adjRoute.EndAirport.AirportCode) && !nonViableRoutes.Contains(adjRoute.RouteNo.ToString()))
                        {//Checks whether or not a path has allready been found to the endairport of the route or if it is marked as non viable
                            SolutionPath solution = new SolutionPath();
                            foreach (Route route in sPath.GetRoutes())
                            {
                                solution.AddRoute(route);
                            }
                            solution.AddRoute(adjRoute);
                            possibleSolutions.Add(solution);
                        }
                    }
                }
                foreach(SolutionPath possibleSolution in possibleSolutions)//Saves the cheapes route of our possible solutions to solutionPath
                {
                    if (possibleSolution.TotalPrice < solutionPath.TotalPrice || solutionPath.TotalPrice == 0)
                    {
                        solutionPath = possibleSolution;
                    }
                }

                if (solutionPath.GetRoutes().Count < maxLayovers + 2 || (solutionPath.GetRoutes().Count == maxLayovers + 2 && solutionPath.GetRoutes().Last().EndAirport.AirportCode == end.AirportCode))
                {//Continue if the current found solution is not at the max layovers amount or if it is, the last routes destination must be our wanted destination.
                    solutionPaths.Add(solutionPath);//Adds the newly found cheapest path to our list of cheapest paths
                    foundPathsTo.Add(solutionPath.Destination().AirportCode);//Marks the destination of the new solutionPath as found
                }
                else
                {
                    nonViableRoutes.Add(solutionPath.GetRoutes().Last().RouteNo.ToString());//Marks the route so we don't try to use it again
                }
                index++;
            }
            if (index == 100)//If we reach our criteria for preventing the while loop from continuing we clear the routes list from the solution we will return
            {
                //Console.WriteLine("Could not find a route to the destination with only {0} layovers", maxLayovers);
                solutionPaths.Last().ClearRoutes();
            }
            solutionPaths.Last().GetRoutes().RemoveAt(0);
            //foreach (Route route in solutionPaths.Last().GetRoutes())
            //{
            //    Console.WriteLine("Going from {0} to {1}", route.StartAirport.Name, route.EndAirport.Name);
            //}
            return solutionPaths.Last().GetRoutes();
        }
    }
}
